
class TreeNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):
        self.root = self._insert(self.root, value)
    
    def _insert(self, node, value):
        if node is None:
            return TreeNode(value)
        if value < node.val:
            node.left = self._insert(node.left, value)
        elif value > node.val:
            node.right = self._insert(node.right, value)
        return node

    def search(self, value):
        return self._search(self.root, value)
    
    def _search(self, node, value):
        if node is None:
            return False
        if value == node.val:
            return True
        elif value < node.val:
            return self._search(node.left, value)
        else:
            return self._search(node.right, value)

    def delete(self, value):
        self.root = self._delete(self.root, value)
    
    def _delete(self, node, value):
        if node is None:  # 边界条件：没找到要删除的节点
            return None
        
        # 递归搜索过程
        if value < node.val:
            node.left = self._delete(node.left, value)
        elif value > node.val:
            node.right = self._delete(node.right, value)
        
        # 找到了要删除的节点
        else:
            # 情况1：无左子节点（直接返回右子树）
            if node.left is None:
                return node.right
            
            # 情况2：无右子节点（直接返回左子树）
            elif node.right is None:
                return node.left
            
            # 情况3：有两个子节点
            else:
                # 查找后继节点（右子树的最小节点）
                min_node = self._min_value_node(node.right)
                # 用后继节点的值替换当前节点的值
                node.val = min_node.val
                # 删除右子树中的后继节点（递归调用）
                node.right = self._delete(node.right, min_node.val)
        
        return node

    def _min_value_node(self, node):
        current = node
        while current and current.left:
            current = current.left
        return current

    def inorder_traversal(self):
        result = []
        self._inorder(self.root, result)
        return result

    def _inorder(self, node, result):
        if node:
            self._inorder(node.left, result)
            result.append(node.val)
            self._inorder(node.right, result)

# 示例用法
if __name__ == "__main__":
    bst = BST()
    nums = [8, 3, 10, 1, 6, 14, 4, 7, 13]
    for num in nums:
        bst.insert(num)
    
    print("中序遍历结果:", bst.inorder_traversal())
    
    print("查找6:", bst.search(6))
    print("查找99:", bst.search(99))
    
    bst.delete(6)
    bst.delete(14)
    print("删除6和14后的中序遍历:", bst.inorder_traversal())